---
title: "性质"
created: 2025-11-28
tags:
  - 算法
---

# 性质

## 树的基本概念与遍历

### 常见遍历方式：

- **前序遍历**：根 -> 左 -> 右
- **中序遍历**：左 -> 根 -> 右
- **后序遍历**：左 -> 右 -> 根
- **层序遍历**：从上到下、从左到右一层一层遍历（借助队列）

### 基本概念：

| 性质/概念 | 简述 |
| --- | --- |
| 树的高度 / 深度 | 根到最远叶子的路径长度 |
| 叶子节点个数 | 没有任何孩子的节点数 |
| 节点总数 = 内部 + 叶子 | 总节点 = 内部节点数 + 叶子节点数 |
| 二叉树的性质 | n个节点的二叉树，最多有n-1条边；满二叉树节点数是奇数等 |
| 递归与DFS/BFS在树中的应用 | 先根、后根等都可以用递归实现；层序使用BFS实现 |
| 线索二叉树、并查集树等 | 数据结构优化的变种 |

## 常见树的类型与特点

| 类型 | 特点 | 示例 |
| --- | --- | --- |
| 普通二叉树 | 每个节点最多两个孩子 | 无特殊结构限制 |
| **完全二叉树** | 每层节点都尽量往左填满，最后一层从左到右连续 | 堆结构就是典型 |
| **满二叉树** | 每个节点要么是叶子节点，要么恰好有两个孩子 | 节点数 = 2^h - 1 |
| **完美二叉树** | 满二叉树 + 最后一层也是满的 | 理想结构，如满堆 |
| **二叉搜索树（BST）** | 中序遍历是有序的 | 左<根<右 |
| **AVL树**（平衡BST） | 任一节点左右子树高度差不超过1 | 高效搜索结构 |
| **红黑树** | 特殊BST，带颜色信息控制平衡，插入删除更高效 | STL中map/set底层实现 |
| **堆**（大根堆/小根堆） | 完全二叉树 + 父子有序性（大于/小于） | 优先队列 |
| **霍夫曼树** | 带权路径最短的树，常用于压缩编码 | Huffman编码 |
| **线段树 / 树状数组** | 用于区间查询、更新问题 | 竞赛常用数据结构 |

## 遍历能否唯一确定一棵树？

| 给定哪些遍历？ | 能否唯一构造树？ |
| --- | --- |
| 中序 + 前序 | ✅ 唯一 |
| 中序 + 后序 | ✅ 唯一 |
| 前序 + 后序 | ❌ 不唯一（除非是**满二叉树**） |
| 单独给中序 / 前序 / 后序 | ❌ 都不唯一 |
| 单独给层序 | ❌ 不唯一 |
| **完全二叉树 + 任意遍历** | ✅ 可以唯一确定（结构固定） |

---
⬅️ [[二叉树|二叉树]] 🏠 [[00-天梯赛]] ➡️ [[L2-007 家庭房产|L2-007 家庭房产]]